const rl = require("readline").createInterface({ input: process.stdin })

/*
* 动态规划 - 找零
* */

class Developer {
  constructor (changeTypes = []) {
    this.changeTypes = changeTypes
    this.cache = {}
  }
  
  getChange (amount) {
    if (amount === 0) return []
  
    if (this.cache[amount]) return this.cache[amount]
    
    let min = []
    
    for (let i = 0; i < this.changeTypes.length; i ++) {
      const leftAmount = amount - this.changeTypes[i]
      
      let leftMin
      if (leftAmount >= 0) {
        leftMin = this.getChange(leftAmount)
      }
      
      if (leftAmount >= 0 && (!min.length || leftMin.length + 1 < min.length)) {
        min = leftMin.concat(this.changeTypes[i])
      }
    }
    
    return this.cache[amount] = min
  }
}

const developer = new Developer([1, 5, 10, 20, 50, 100])

rl.on('line', (line) => {
  
  console.log(developer.getChange(parseInt(line)))
})

rl.on('close', () => {

})
